package com.peng.heap;

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

import static com.study.class07.Code01_CoverMax.generateLines;

/**
 * 线段最大重合问题：
 * 给定很多线段，每个线段都有两个数[start, end]，
 * 表示线段开始位置和结束位置，左右都是闭区间
 * 规定：
 * 1）线段的开始和结束位置一定都是整数值
 * 2）线段重合区域的长度必须>=1
 * 返回线段最多重合区域中，包含了几条线段
 */
public class Test02_MaxCover {

    public static void main(String[] args) {
        System.out.println("test begin");

        int N = 100;
        int L = 0;
        int R = 200;
        int testTimes = 200000;
        for (int i = 0; i < testTimes; i++) {
            int[][] lines = generateLines(N, L, R);
            int ans1 = comparator(lines);
            int ans2 = maxCover(lines);
            if (ans1 != ans2) {
                System.out.println("Oops!");
            }
        }
        System.out.println("test end");
    }


    public static int maxCover(int[][] lines) {
        Line[] lineArr = new Line[lines.length];
        for (int i = 0; i < lines.length; i++) {
            lineArr[i] = new Line(lines[i][0], lines[i][1]);
        }

        Arrays.sort(lineArr, Comparator.comparingInt(o -> o.start));

        PriorityQueue<Integer> heap = new PriorityQueue<>();


        int cover = 0;
        for (Line line : lineArr) {
            while (!heap.isEmpty() && line.start >= heap.peek()) {
                heap.poll();
            }
            heap.add(line.end);
            cover = Math.max(cover, heap.size());
        }

        return cover;


    }

    public static int comparator(int[][] lines) {

        int min = Integer.MAX_VALUE;
        int max = Integer.MIN_VALUE;
        for (int[] line : lines) {
            min = Math.min(min, line[0]);
            max = Math.max(max, line[1]);
        }

        int maxCount = 0;
        for (double point = min + 0.5; point < max; point++) {
            int cover = 0;
            for (int[] line : lines) {
                if (line[0] < point && line[1] > point) {
                    cover++;
                }
            }
            maxCount = Math.max(cover, max);
        }

        return maxCount;

    }

    private static class Line {
        int start;
        int end;

        public Line(int start, int end) {
            this.start = start;
            this.end = end;
        }
    }
}
